package _2022.hot100._322_零钱兑换;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author： YHSimon
 * @date： 2022-05-29 08:54
 */
public class Solution {
    // 超时
    public int ans = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        List<Integer> combine = new ArrayList<>();
        Arrays.sort(coins);
        dfs(coins, combine, coins.length - 1, amount);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private void dfs(int[] coins, List<Integer> combine, int start, int amount) {
        if (amount < 0) {
            return ;
        }
        if (amount == 0) {
            // System.out.println(combine.toString());
            ans = Math.min(ans, combine.size());
            return;
        }
        for (int i = start; i >= 0; i--) {
            combine.add(coins[i]);
            dfs(coins, combine, i, amount - coins[i]);
            combine.remove(combine.size() - 1);
        }

    }

    public static void main(String[] args) {
        Solution s = new Solution();
        // System.out.println(s.coinChange(new int[]{1,2,5}, 11));
        // System.out.println(s.coinChange(new int[]{2,5,10,1}, 27));
        System.out.println(s.coinChange(new int[]{186, 419, 83, 408}, 6249));
    }
}
